package ListaHash;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * @author Christopher Rieder. Legajo 52915.
 */
public class HashTable<T> implements Iterable<T>{

    private Estado[] estados;
    //LOS NODOS VACIOS O TUMBAS APUNTAN A NULL; AL ACCEDER A UN NODO, SIEMPRE
    //ASEGURARSE DE QUE ESTE OCUPADO.
    private Nodo<T>[] nodos;
    private int nodosLibres;
    private double factorDeCarga;
    private int maxLoad;

    public HashTable(double factorDeCarga, int tamañoInicial){
        tamañoInicial = siguientePrimo(tamañoInicial);
        if(factorDeCarga > 0.5)
            this.factorDeCarga = 0.5;
        else
            this.factorDeCarga = factorDeCarga;

        nodos = new Nodo[tamañoInicial];
        estados = new Estado[tamañoInicial];

        for (int i = 0 ; i < tamañoInicial ; i++){
            estados[i] = Estado.LIBRE;
        }
        maxLoad = (int)(nodos.length * factorDeCarga);
        nodosLibres = tamañoInicial;
    }

    public HashTable(){
        this(0.5, 1000);
    }

    public boolean insertar(T x){
        int hash = Math.abs(x.hashCode()) % nodos.length;
        
        int aux = 1;
        boolean recorrerHash = true;
        boolean encontrado = false;
        boolean insertado = false;
        do{
            switch(estados[hash]){
                case OCUPADO:
                    if(nodos[hash].info.equals(x)){
                        encontrado = true;
                        recorrerHash = false;
                        break;
                    }
                    //Si no es el que busco, continuo nomás e incremento,
                case TUMBA:    //no hace el break en OCUPADO
                    aux++;
                    hash = hash + aux*aux;
                    if(hash >= nodos.length){
                        hash = hash % nodos.length;
                    }
                    break;
                case LIBRE: recorrerHash = false; break;
            }
        }while(recorrerHash);

        if(!encontrado){
            //insertamos en hash.
            nodos[hash] = new Nodo(x);
            nodosLibres--;
            estados[hash] = Estado.OCUPADO;
            if(nodos.length - nodosLibres > maxLoad)
                resize(siguientePrimo(nodos.length * 2));
            insertado = true;
        }
        return insertado;
    }

    public T buscar(T x){
        int posicion = getPosición(x);
        T aux;
        if(posicion == -1)
            aux = null;
        else
            aux = nodos[posicion].info;
        return aux;
    }

    private int getPosición(T x){
        int hash = x.hashCode() % nodos.length;
        int aux = 1;
        boolean recorrerHash = true;
        boolean encontrado = false;
        while(recorrerHash){
            switch(estados[hash]){
                case OCUPADO:
                    if(nodos[hash].info.equals(x)){
                        encontrado = true;
                        recorrerHash = false;
                        break;
                    }
                case TUMBA:
                    aux++;
                    hash = hash + aux*aux;
                    if(hash >= nodos.length){
                        hash = hash % nodos.length;
                    }
                    break;
                case LIBRE: recorrerHash = false; break;
            }
        }
        if(encontrado)
            return hash;
        else
            return -1;
    }

    public boolean contiene(T x){
        return getPosición(x) != -1;
    }

    public boolean eliminar(T x){
        int posicion = getPosición(x);
        boolean borrado = false;
        if(posicion != -1){
            nodos[posicion] = null;
            estados[posicion] = Estado.TUMBA;
            borrado = true;
        }
        return borrado;
    }

    public void resize(int size){
        int nuevoTamaño = size;
        System.out.println("Resize to: " + nuevoTamaño);

        Estado[] newEstados = new Estado[nuevoTamaño];
        Nodo<T>[] newNodos = new Nodo[nuevoTamaño];
        int newNodosLibres = nuevoTamaño;

        //Todos los nuevos estados son libres.
        
        for(int i = 0 ; i < nuevoTamaño ; i++){
            newEstados[i] = Estado.LIBRE;
        }


        //Y para cada nodo ocupado en el viejo hash, se hashea de vuelta con el
        //nuevo tamaño y se inserta al nuevo hash
        for(int i = 0 ; i < nodos.length ; i++){
            if(estados[i] == Estado.OCUPADO){
                int newHash = nodos[i].info.hashCode() % nuevoTamaño;
                newEstados[newHash] = Estado.OCUPADO;
                newNodos[newHash] = nodos[i];
                newNodosLibres--;
            }
        }

        this.estados = newEstados;

        this.nodos = newNodos;
        this.nodosLibres = newNodosLibres;
        this.maxLoad = (int)(nodos.length * factorDeCarga);
    }
    
    private static final int siguientePrimo(int n){
        n++;
        if(n%2 == 0 ) n++;
        while(!esPrimo(n))
            n+=2;
        return n;
    }


    //Entre 3 y sqrt(n) ver si es divisor.
    private static boolean esPrimo(int n) {
        boolean aux = true;
        int raizn = (int) Math.sqrt(n);
        for(int i = 3 ; i <= raizn && aux; i += 2)
            if( n%i == 0)
                aux = false;
        return aux;
    }

    @Override
    public String toString(){
        String aux = "";
        for(int i = 0 ; i < nodos.length ; i++){
            
            if(estados[i] == Estado.OCUPADO){
                aux += nodos[i].info.toString() + "\n";
            }
        }
        return aux;
    }

    public Iterator<T> iterator(){
        return new Iterador();
    }


    private class Nodo<T>{
        T info;

        public Nodo(T info){
            this.info = info;
        }
    }

    private enum Estado{
        LIBRE,
        OCUPADO,
        TUMBA
    }


    private class Iterador implements Iterator<T>{

        private int index = -1;
        private boolean hasRemoved = false;

        public Iterador(){

        }

        public boolean hasNext() {
            int i = index;
            i++;
            boolean recorrer = true;
            while(i < nodos.length && recorrer){
                if(estados[i].equals(Estado.OCUPADO))
                    recorrer = false;
                else
                    i++;
            }

            return i < nodos.length;
        }

        public T next() throws NoSuchElementException{
            index++;
            boolean recorrer = true;
            while(index < nodos.length && recorrer){
                if(estados[index].equals(Estado.OCUPADO))
                    recorrer = false;
                else
                    index++;
            }
            if(index >= nodos.length)
                throw new NoSuchElementException();

            hasRemoved = false;
            return nodos[index].info;
        }

        public void remove() {
            if(hasRemoved)
                throw new IllegalStateException();
            nodos[index] = null;
            estados[index] = Estado.TUMBA;
            hasRemoved = true;
        }

    }
    
}


